package easy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Solution_590 {

    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(root);

        while (!stack.empty()) {
            Node node = stack.pop();
            if (node.children == null || node.children.size() == 0) {
                list.add(node.val);
            } else {
                stack.add(node);
                int size = node.children.size();
                for (int i = size-1; i >= 0; i--) {
                    stack.add(node.children.get(i));
                }
                node.children = null;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Solution_590 model = new Solution_590();
        Node node = new Node(1);

        List<Node> list1 = new ArrayList<>();
        Node node1 = new Node(3);
        list1.add(node1);
        Node node2 = new Node(2);
        list1.add(node2);
        Node node3 = new Node(4);
        list1.add(node3);
        node.children = list1;

        List<Node> list2 = new ArrayList<>();
        Node node4 = new Node(5);
        list2.add(node4);
        Node node5 = new Node(6);
        list2.add(node5);
        node1.children = list2;

        System.out.println(model.postorder(node));
        System.out.println(model.postorder(null));
    }

    static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}
